75D - Big Maximum Sum - CodeForces Solution

#include<bits/stdc++.h>
#include<algorithm>
#include <vector>
#include<bitset>
// bitmasks
#define ll long long
#define mod 1000000007
#define MOD1 998244353
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0)

using namespace std;

void solve(){

    ll n,m;
    cin>>n>>m;

    vector<ll> pre[n+1];
    vector<pair<ll,ll>> new_era(n+1,{0,0});
    ll ind=1;
    vector<pair<ll,ll>> dp(n+1,{INT_MIN,INT_MIN});

    while(n--){

        ll l;
        cin>>l;
        
        ll a[l+1];
        ll maxx=INT_MIN,sum=0,temp=0;
        ll ans=INT_MIN;
        ll index=0;
        for(int i=1; i<=l; i++){
            cin>>a[i];
            if(i==0){
                pre[ind].pb(a[i]), sum+=a[i];
                maxx=max(maxx,a[i]);
                temp=a[i];
                ans=a[i];
                index=1;
            }
            else{
                pre[ind].pb(sum+a[i]);
                sum+=a[i];
                temp=a[i];
                maxx=max(a[i], maxx+a[i]);
                if(maxx>ans){
                    index=i;
                }
                ans=max(ans,maxx);
                
            }  
            if(dp[ind].ff <sum || i==1){
                dp[ind].ff=sum;
            }
        }
        new_era[ind]={ans,maxx};
        dp[ind].ss=sum;
        
        ind++;
    }

    ll sequence[m+1];
    for(int i=1; i<=m; i++){
        cin>>sequence[i];
    }

    ll ans=INT_MIN;
    ll flag=1;
    ll until=INT_MIN, till_now=INT_MIN;
    for(int i=1; i<=m; i++){

        ll start=new_era[sequence[i]].ff;
        ll end=new_era[sequence[i]].ss;

        until=till_now+dp[sequence[i]].ff;
        till_now=till_now+dp[sequence[i]].ss;
        ans=max(ans,max(until,start));

        if(till_now<0 || till_now<end){
            ans=max(end,ans);
            till_now=new_era[sequence[i]].ss;
        }

    }
    cout<<ans<<endl;
}

int main(){
    
    fastio();
    ll t=1;
    // cin>>t;
    while(t--){
        solve();
    }
}